730J - Bottles - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define fastio()                      \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);                    \
cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#define PI 3.141592653589793238462
#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
const double pi = 3.14159265358979323846;
const int M = 1e6 + 1;
vector<int> adj[M];
bool gone[M];
void pre_code()
{
      fastio();
}
void solve()
{
    ll n;
    cin>>n;
    vector<pair<ll,ll>>v1(n);
    ll sum = 0;
    ll tot1 = 0,tot2 = 0;
    ll cnt = 0;
    for(ll i=0;i<n;i++)
    {
        cin>>v1[i].second;
        tot1 += v1[i].second;
    }
    // cout<<tot1<<" = tot1\n";
    for(ll i=0;i<n;i++)
    {
        cin>>v1[i].first;
        sum += v1[i].first;
    }
    sort(v1.begin(),v1.end());
    for(ll i=n-1;i>=0;i--)
    {
        tot2 += v1[i].first;
        cnt++;
        if(tot2>=tot1)
        {
            break;
        }
    }
    cout<<cnt<<" ";
    vector<vector<ll>>dp(cnt+1,vector<ll>(sum+1,INT_MIN));
    // vector<vector<vector<ll>>>dp(n+2,vector<vector<ll>>(cnt+1,vector<ll>(sum+1,INT_MIN)));
    // ll dp[n+2][cnt+1][sum+1];
    // memset(dp,INT_MIN,sizeof(dp));
    dp[0][0] = 0;
    // for(int i=0;i<=n;i++)
    // {
    //     dp[0][0] = 0;
    // }
    ll fans = 0;
    for(ll i=1;i<=n;i++)
    {
        // dp[i][0][0] = 0;
        for(ll j=(i,cnt);j>=1;j--)
        {
            for(ll k=sum;k>=1;k--)
            {
                if(k>=v1[i-1].first&&dp[j-1][k-v1[i-1].first]!=INT_MIN)
                {
                    // cout<<"oye\n";
                    dp[j][k] = max(dp[j][k],dp[j-1][k-v1[i-1].first]+v1[i-1].second);
                    if(j==cnt&&k>=tot1)
                    {
                        // cout<<"oye\n";
                        fans = max(fans,dp[j][k]);
                        // dp[i+1][j][k] = dp[i][j][k];
                    }
                }
                // dp[j][k] = max(dp[j][k],dp[i-1][j][k]);
            }
        }
    }
    cout<<tot1-fans<<"\n";
}
int main()
{
    pre_code();
    int freq = 1;
    // cin >> freq;
    while (freq--)
    {
        solve();

    }
}
// Life sucks when code bugs  -- "Sumit Negi"